#include<stdio.h>
#include<stdlib.h>
#include"linklist.h"
#define true 1
#define false 0

void InitLinkList(struct LinkList *list)
{
    list->len=0;
    list->head=NULL;
}

struct Node *CreateNode()
{
    struct Node *NewNode=(struct Node*)malloc(sizeof(struct Node));
    NewNode->next=NULL;
    return NewNode;
}


int InsertTail(struct LinkList *list, Node_ElemenType element)
{
    //create a new node
    struct Node *NewNode=CreateNode();
    if(NewNode==NULL)
    {
        printf("Node malloc error!\n");
        return false;
    }
    NewNode->data=element;

    //find tail
    struct Node *TravelPoint=list->head;
    if(TravelPoint==NULL)
    {
        list->head=NewNode;    
    }
    else
    {
        while(TravelPoint->next!=NULL)
        {
            TravelPoint=TravelPoint->next;
        }
        TravelPoint->next=NewNode;
    }
    list->len++;
    
    return true;
}

int InsertHead(struct LinkList *list, Node_ElemenType element)
{
    //create a new node
    struct Node *NewNode=CreateNode();
    if(NewNode==NULL)
    {
        printf("Node malloc error!\n");
        return false;
    }
    NewNode->data=element;

    NewNode->next=list->head;
    list->head=NewNode;
    list->len++;
    return 0;
}

int InsertIndex(struct LinkList *list, Node_ElemenType element, int index)
{
    if(index<0 || index>list->len)
    {
        printf("InsertIndex invalid space!\n");
        return false;
    }

    //create a new node
    struct Node *NewNode=CreateNode();
    if(NewNode==NULL)
    {
        printf("Node malloc error!\n");
        return false;
    }
    NewNode->data=element;

    if(list->head==NULL)
    {
        if(index!=0)
        {
            printf("linklist is empty!you can only insert index 0!\n");
            free(NewNode);
            return false;
        }
        else
        {
            list->head=NewNode;
            list->len++;
            return true;
        }
    }

    int count=0;
    struct Node *TravelPoint =list->head;
    if(index==0)
    {
        NewNode->next=TravelPoint;
        list->head=NewNode;
        list->len++;
        return true;
    }
    while(count<index-1)
    {
        TravelPoint=TravelPoint->next;
        count++;
    }
    NewNode->next=TravelPoint->next;
    TravelPoint->next=NewNode;
    list->len++;
    return true;
}

void FreeLinkList(struct LinkList *list)
{
    while(list->head!=NULL)
    {
        struct Node *nextNode=list->head->next;
        free(list->head);
        list->head=nextNode;
    }
    list->len=0;
}

void RemoveByIndex(struct LinkList *list,int index)
{
    if(index<0 || index>=list->len)
    {
        printf("invalid space!\n");
        return;
    }

    if(index==0)
    {
        struct Node *FreeNode=list->head;
        list->head=list->head->next;
        free(FreeNode);
        list->len--;
        return;
    }

    int count=0;
    struct Node *TravelPoint=list->head;
    while(count<index-1)
    {
        TravelPoint=TravelPoint->next;
        count++;
    }
    struct Node *FreeNode=TravelPoint->next;
    TravelPoint->next=TravelPoint->next->next;
    free(FreeNode);
    list->len--;
}

void RemoveByElement(struct LinkList *list, Node_ElemenType element)
{
    if(list->len==0)
        return;
    struct Node *TravelPoint=list->head;

    while(TravelPoint->next!=NULL)
    {
        if(TravelPoint->next->data==element)
        {
            struct Node *FreeNode =TravelPoint->next;    
            TravelPoint->next=TravelPoint->next->next;
            free(FreeNode);
            list->len--;
        }
        else
        {
            TravelPoint=TravelPoint->next;
        }
        // TravelPoint=TravelPoint->next;
    }

    if(list->head->data==element)
    {
        struct Node *FreeNode =list->head;    
        list->head=list->head->next;
        free(FreeNode);
        list->len--;       
    }
}

Node_ElemenType *FindByIndex(struct LinkList *list, int index)
{
    if(index<0 || index>=list->len)
    {
        printf("find invalid space!\n");
        return NULL;
    }   

    struct Node *TravelPoint=list->head; 
    int count=0;
    while(count<index)
    {
        TravelPoint=TravelPoint->next;
        count++;
    }
    return &TravelPoint->data;
}

int *FindByElement(struct LinkList *list, Node_ElemenType element)
{
    int *findVector=(int *)malloc(sizeof(int)*(list->len+1));
    if(findVector==NULL)
    {
        printf("findByElement malloc error!\n");
        return NULL;
    } 

    struct Node *TravelPoint=list->head; 
    int count=0;
    int k=0;
    while(TravelPoint!=NULL)
    {
        if(TravelPoint->data==element)
        {
            findVector[k]=count;
            k++;
        }
        TravelPoint=TravelPoint->next;
        count++;
    }

    findVector[k]=-1;
    return findVector;
}

void SetValueByIndex(struct LinkList *list, Node_ElemenType element, int index)
{
    if(index<0 || index>=list->len)
    {
        printf("setValueIndex invalid space!\n");
        return;
    }      

    struct Node *TravelPoint=list->head; 
    while(index!=0)
    {
        TravelPoint=TravelPoint->next;
        index--; 
    }
    TravelPoint->data=element;
}

void SetValueByElement(struct LinkList *list, Node_ElemenType oldvalue, Node_ElemenType newvalue)
{
    struct Node *TravelPoint=list->head; 
    while(TravelPoint!=NULL)
    {
        if(TravelPoint->data==oldvalue)
        {
            TravelPoint->data=newvalue;
        }
        TravelPoint=TravelPoint->next;
    } 
}



void BubbleSort(struct LinkList *list)
{
    InsertHead(list,0);
    
    for(int i=0;i<list->len-1-1;i++)
    {
        struct Node *TravelPoint=list->head; 
        for(int j=0;j<list->len-i-1-1;j++)
        {
            if(TravelPoint->next->data > TravelPoint->next->next->data)
            {
                struct Node *Prev=TravelPoint->next;
                struct Node *Next=TravelPoint->next->next;

                Prev->next=Next->next;
                Next->next=Prev;
                TravelPoint->next=Next;
            }
            TravelPoint=TravelPoint->next;
        }
    }
    RemoveByIndex(list,0);
}

void Reserve(struct LinkList *list)
{
    struct Node *prev=NULL;
    struct Node *cur=list->head;
    struct Node *Next=list->head->next;

    while(Next!=NULL)
    {
        cur->next=prev;
        prev=cur;
        cur=Next;
        Next=cur->next;
    }

    cur->next=prev;
    list->head=cur;
}

struct Node *Reserves2(struct Node *node)
{
    struct Node *tail;
    if(node->next==NULL)
    {
        return node;
    }
    else
    {
        tail=Reserves2(node->next);
        node->next->next=node;
        node->next=NULL;
        return tail;
    }
}

void Travel(struct LinkList *list)
{
    printf("list len:%d\n",list->len);
    struct Node *TravelPoint=list->head;
    if(TravelPoint==NULL)
    {
        return;    
    }
    else
    {
        while(TravelPoint!=NULL)
        {
            printf("%d ",TravelPoint->data);
            TravelPoint=TravelPoint->next;
        }
    }
    printf("\n");
}

